/**
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 */

/** 解题思路 **/


// 1. 简单递归（超出时间限制。缺点：大量重复的计算）
let fib = function(n) {
    if (n < 2) {
        return n
    }
    return (fib(n - 1) + fib(n - 2)) % 1000000007
}

// 2. 改进版递归（通过，用数组或者字典暂存计算过的值）
let fib = function(n, arr = []) {
    if (n < 2) {
        return n
    }
    if (arr[n]) {
        return arr[n]
    }
    let a = fib(n - 1, arr);
    arr[n - 1] = a;
    let b = fib(n - 2, arr);
    arr[n - 2] = b;
    let res = (a + b) % 1000000007;
    arr[n] = res;
    return res;
}

// 3. 非递归 （动态规划）
let fib = function(n) {
    if (n < 2) {
        return n;
    }
    let [a, b] = [0, 1]
    for (let i = 2; i <= n; i++) {
        // let temp = a;
        // a = b;
        // b = (temp + b) % 1000000007

        [a, b] = [b, (a + b) % 1000000007]
    }
    return b;
}

// 3.1 非递归（更简洁）
let fib = function(n) {
    let [a, b, i] = [0, 1, 0]
    while (i < n) {
        [a, b] = [b, (a + b) % 1000000007];
        i++;
    }
    return a;
}